#include<iostream>
#include<string>
#include<map>
#include<unordered_map>
#include<list>
#include<utility>

class LRUCache {
public:
    LRUCache(int capacity) 
        :_max(capacity+1)
    {
    }
    int get(int key) {
        if(!_cache.count(key))
        {
            return -1;
        }
        _time.splice(_time.begin(),_time,_cache[key]);
            _cache[key]=_time.begin();
        return (*_cache[key]).second;
    }
    void put(int key, int value) {
        if(!_cache.count(key))
        {
        _cache[key]=_time.insert(_time.begin(),std::make_pair(key,value));
        }
        else
        {
            _time.splice(_time.begin(),_time,_cache[key]);
            _cache[key]=_time.begin();
        }
        if(_time.size()==_max)
        {
            auto it =_time.back();
            _cache.erase(it.first);
            _time.pop_back();
        }
    }
private:
    size_t _max=10;
    std::unordered_map<int,std::list<std::pair<int,int>>::iterator> _cache;
    std::list<std::pair<int,int>> _time;

};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

int main(void)
{
LRUCache lRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
}
